#include<bits/stdc++>
using namespace std;

// 【题目】力扣1337.矩阵中战斗力最弱的K行
// 【难度】简单
// 【提交】https://leetcode.cn/problems/the-k-weakest-rows-in-a-matrix/submissions/669084888/?envType=problem-list-v2&envId=binary-search
// 【标签】数组；二分查找；矩阵；排序；堆（优先队列）

class Solution {
public:
    vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
        int m = mat.size(), n = mat[0].size();
        vector<pair<int, int>> power;
        for (int i = 0; i < m; ++i) {
            int l = 0, r = n - 1, pos = -1;
            while (l <= r) {
                int mid = (l + r) / 2;
                if (mat[i][mid] == 0) {
                    r = mid - 1;
                }
                else {
                    pos = mid;
                    l = mid + 1;
                }
            }
            power.emplace_back(pos + 1, i);
        }

        priority_queue q(greater<pair<int, int>>(), move(power));
        vector<int> ans;
        for (int i = 0; i < k; ++i) {
            ans.push_back(q.top().second);
            q.pop();
        }
        return ans;
    }
};
